/**
 *  Copyright (C) 2013  Piotr Szczepa�ski
 *
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/
package edu.pw.elka.gtsna.graph;

import java.util.HashMap;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;
import java.util.Vector;

import edu.pw.elka.gtsna.community_detection.CommunityStructure;
import edu.pw.elka.gtsna.graph_creator.GraphCreator;

/**
 * @author Piotr Lech Szczepa�ski
 * @author P.Szczepanski@ii.pw.edu.pl 
 *
 */
public abstract class Graph implements Cloneable {
	protected Set<Integer>[] graphNeighbours;
	
	protected int numOfNodes;
	protected int numOfEdges;
	
	/**
	 * This is a map from nodes label to its position
	 */
	Map<Integer,Integer> nodeTOpos;
	
	/**
	 * This is a map from nodes position to its label 
	 */
	Map<Integer,Integer> posTOnode;
	
	private int freePosition=0;
	
	protected void getFreePosition(int label){
		if (nodeTOpos.get(label) == null){
			nodeTOpos.put(label, freePosition);
			posTOnode.put(freePosition, label);
			freePosition++;
		} 
	}
	
	public abstract Graph clone() throws CloneNotSupportedException;
	
	
	@SuppressWarnings("unchecked")
	public Graph(int numOfNodes){
		graphNeighbours = new Set[numOfNodes];
		nodeTOpos = new HashMap<Integer,Integer>();
		posTOnode = new HashMap<Integer,Integer>();
		this.numOfNodes = numOfNodes;
		this.numOfEdges = 0;
		
		for (int i = 0; i< numOfNodes; i++){
			graphNeighbours[i] = new LinkedHashSet<Integer>();
		}
	}
	

	@SuppressWarnings("unchecked")
	public Graph(Graph gr){
		this.graphNeighbours = new Set[gr.getNumOfNodes()+1];
		this.nodeTOpos = (Map<Integer, Integer>)((HashMap<Integer, Integer>)gr.nodeTOpos).clone();
		this.posTOnode = (Map<Integer, Integer>)((HashMap<Integer, Integer>)gr.posTOnode).clone();
		this.numOfNodes = gr.getNumOfNodes();
		this.numOfEdges = gr.getNumOfEdges();
		
		for (int node: gr.getAllNodes()){
			graphNeighbours[pos(node)] = new LinkedHashSet<Integer>(gr.getNeigbours(node));
		}
	}
	
	/**
	 * 
	 * @param node
	 * @return Returns normalized position of the node (0 to |V|)
	 */
	public int pos(int node){
		return nodeTOpos.get(node);
	}
	
	/**
	 * 
	 * @param position
	 * @return Returns the node at normalized position
	 */
	public int node(int position){
		return posTOnode.get(position);
	}
	
	
	public Set<Integer> getAllNodes() {
		Set<Integer> nodes = new LinkedHashSet<Integer>(nodeTOpos.keySet());	
		return nodes;
	}
	
	protected void addEdge(int u, int v){
		getFreePosition(u);
		getFreePosition(v);
		if (!areNeighbours(u, v)){
			numOfEdges++;
			graphNeighbours[pos(u)].add(v);
		}
	}
	
	public void removeNode(int node){
		Set<Integer> neighbours = new LinkedHashSet<Integer> (getNeigbours(node));
		for(int neighbour: neighbours){
			removeEdge(node,neighbour);
		}
		graphNeighbours[pos(node)]=graphNeighbours[numOfNodes-1];
		graphNeighbours[numOfNodes-1]=null;
		//System.out.println("pozycja "+(numOfNodes+1)+" get NULL");
		
		nodeTOpos.put(node(numOfNodes-1), pos(node)); 
		posTOnode.put(pos(node), node(numOfNodes-1));
		nodeTOpos.remove(node);
		posTOnode.remove(numOfNodes-1);
		
		numOfNodes--;
	}
	
	public void isolateNode(int node){
		Set<Integer> neighbours = new LinkedHashSet<Integer> (getNeigbours(node));
		for(int neighbour: neighbours){
			removeEdge(node,neighbour);
		}
	}
	
	protected void removeEdge(int u, int v){
		numOfEdges--;
		graphNeighbours[pos(u)].remove(v);
	}
	
	public void addEdge(Edge edge){
		addEdge(edge.getFrom(), edge.getTo());
	}
	
	public void removeEdge(Edge edge){
		removeEdge(edge.getFrom(), edge.getTo());
	}
	
	public Boolean hasEdge(Edge edge){
		return areNeighbours(edge.getFrom(), edge.getTo());
	}
	
	public Boolean areNeighbours(int n1, int n2){
		return graphNeighbours[pos(n1)].contains(n2);
	}
	
	public Set<Integer> getNeigbours(int node){
		return graphNeighbours[pos(node)];
	}
	
	public int getDegree(int node){
		return graphNeighbours[pos(node)].size();
	}
	
	
	// TODO  Move functions involving community structure to Community Structure
	// *************************************************************************
	public int getInterCommunityDegree(int node, CommunityStructure cs){
		int degree = 0;
		boolean checked[] = new boolean[cs.size()];
		for(int neighbour: getNeigbours(node)){
			if (!checked[cs.getNodeCommunityNumber(neighbour)]){
				degree++;
				checked[cs.getNodeCommunityNumber(neighbour)] = true;
			}
		}
		// do not count nodes from the same cs
		if (checked[cs.getNodeCommunityNumber(node)]) {
			degree--;
		}
		return degree;
	}
	
	public int getIntraCommunityDegree(int node, CommunityStructure cs){
		return getIntraCommunityDegree(node,cs,cs.getNodeCommunityNumber(node));
	}
	
	public int getIntraCommunityDegree(int node, CommunityStructure cs, int partitionNumber ){
		int degree = 0;
		for(int neighbour: getNeigbours(node)){
			if (partitionNumber == cs.getNodeCommunityNumber(neighbour)){
				degree++;
			}
		}
		return degree;
	}
	
	public int getInterPartitionDegree(int node, CommunityStructure cs){
		int degree = 0;
		for(int neighbour: getNeigbours(node)){
			if (cs.getNodeCommunityNumber(node) != cs.getNodeCommunityNumber(neighbour)){
				degree++;
			}
		}
		return degree;
	}
	
	// *************************************************************************
	
	
	public int getNumOfNodes() {
		return numOfNodes;
	}

	public Set<Integer> getNeigbours(Set<Integer> subgraph){
		Set<Integer> N = new LinkedHashSet<Integer>();
		for(int i : subgraph) {
			for (int u: getNeigbours(i)){
				if (!subgraph.contains(u)) {
					N.add(u);
				}
			}
		}
		return N;
	}
	
	public int getNumOfEdges() {
		return numOfEdges;
	}
	
	public void print(){
		for (int node: this.getAllNodes()){
			System.out.println(node+": "+this.getNeigbours(node));
		}
	}
	

	
	
}
